package leetcode.L500;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @Description ex212 单词搜索2
 * @Author yangshunjie
 * @Date 2021/9/16
 */
public class Ex212 {
    int n;
    int m;
    public List<String> findWords(char[][] board, String[] words) {

        n = board.length;
        m = board[0].length;
        List<String> res = new ArrayList<>();
        Set<String> set = new HashSet<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            int[][] used = new int[n][m];
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    if(dfs(board,used,word,0,k,j)&&set.add(word)){
                        res.add(word);
                        break;
                    }
                }
            }
        }
        return res;
    }

    public Boolean dfs(char[][] board,int[][] used,String word,int i,int x,int y){
        if(word.length()==i){
            return true;
        }
        if(x>=0&&y>=0&&x<m&&y<n&&board[y][x]==word.charAt(i)&&used[y][x]==0){
            used[y][x] = 1;
            Boolean b1 = dfs(board,used,word,i+1,x+1,y);

            Boolean b2 =dfs(board,used,word,i+1,x,y+1);

            Boolean b3 =dfs(board,used,word,i+1,x-1,y);

            Boolean b4 =dfs(board,used,word,i+1,x,y-1);
            used[y][x] = 0;
            return b1||b2||b3||b4;
        }
        return false;
    }

    public static void main(String[] args) {
        // char[][] board = {{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}};
        // String[] word = {"oath","pea","eat","rain"};

        char[][] board = {{'a','b'}};
        String[] word = {"ba"};
        Ex212 ex212 = new Ex212();
        List<String> words = ex212.findWords(board, word);
        System.out.println(words.get(0));
    }

}
